package sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * 插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表，
 * 开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出
 * 第一个元素，在有序表中从后往前进行比较，将它插入到有序表中的适当位置，
 * 使之成为新的有序表。
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {344,656,54,324,12,3445,6566,546};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    /*
    1. i循环从下标1开始递增到末尾
    2. i位置值先拿出来存到一个临时变量
    3. j循环从i-1递减一直到0位置
    4. j循环中，j位置的值>tmp，j位置的值复制到j+1位置
    5. j位置值不大,j循环结束
    6. j循环结束，临时值放到j+1位置
     */
    private static void sort(int[] a){
        //从第二个元素开始，和前面的有序表进行比较
        for (int i = 1; i < a.length; i++) {
            int tem = a[i];//记录要插入的值，将待插入的值取出并保存在tem中，防止数据移动时该元素丢失
            int j;
            //从后往前进行遍历比较
            for (j = i-1; j >= 0 ; j--) {
                if (tem<a[j]){
                    a[j+1] = a[j];//后移一个位置
                }else {
                    break;
                }
            }
            a[j+1] = tem;//遍历完有序表所有大于tem的元素后，将tem插入
        }
    }

    private static void sort1(int[]a){
        for (int i = 1; i < a.length; i++) {
            int tem = a[i];
            int j;
            for ( j = i-1; j >=0 ; j--) {
                if (a[j]>tem){
                    a[j+1] = a[j];
                }else {
                    break;
                }
            }
            a[j+1] = tem;
        }
    }

}
